In order to transmit or store digitized audio, the audio must be encoded to a digital form. In doing so, the analog audio is digitized to form a vector or matrix. The digitized audio is then encoded in order to reduce the amount of information required to digitally represent the audio. Methods for encoding (coding) vector or matrix quantities for speech, audio, image, video, and other signals are well known. One such method described in U.S. Pat. No. 6,236,960 by Peng, et.al, (which is incorporated by reference herein) is known as Factorial Pulse Coding (or FPC). If elements of vector x are constrained such that −m≦xi≦m, and values of xi, are integral, then FPC can produce a codeword for a vector x using a total of M bits, given that:
                              m          =                                    ∑                              i                =                0                                            n                -                1                                      ⁢                                                        x                i                                                                  ,                            (        1        )            where m is the total number of unit amplitude pulses, and n is the vector length. For the N possibilities for vector x, the total M bits are used to code N combinations of vector x in a maximally efficient manner, such that the following expression, which describes the theoretical minimum number of combinations, holds true:
                    N        =                                            ∑                              d                =                1                                            min                ⁡                                  (                                      m                    ,                    n                                    )                                                      ⁢                                          F                ⁡                                  (                                      n                    ,                    d                                    )                                            ⁢                              D                ⁡                                  (                                      m                    ,                    d                                    )                                            ⁢                              2                d                                              ≤                                    2              M                        .                                              (        2        )            
For this equation, F(n,d) is a combinatorial function, having the number of combinations of d non-zero vector elements over n positions given by:
                              F          ⁡                      (                          n              ,              d                        )                          =                                            n              !                                                      d                !                            ⁢                                                (                                      n                    -                    d                                    )                                !                                              .                                    (        3        )            D(m,d) are the number of combinations of d non-zero vector elements given m total unit pulses given by:D(m,d)=F(m−1, d−1)  (4)and 2d represents the combinations required to describe the polarity (sign) of the d non-zero vector elements. In the above equations n comprises a position parameter, d comprises a pulse index parameter. A method and apparatus for coding and decoding vectors described above have been fully described in the prior art. Furthermore, a practical implementation of this coding method has been described in 3GPP2 standard C.S0014-B, where the vector length n=54 and the number of unit magnitude pulses m=7 produce an M=35 bit codeword.
While these low values of n and m do not cause any unreasonable complexity burden, larger values can quickly cause problems, especially in mobile handheld devices which need to keep memory and computational complexity as low as possible. For example, use of this coding method for some applications (such as audio coding) may require n=144 and m=28, or higher. Under these circumstances, the cost associated with producing the combinatorial expression F(n,d) can be quite high.
Let us rewrite Eq. 3 as:
                              F          ⁡                      (                          n              ,              d                        )                          =                                                            ∏                                  i                  =                                      n                    -                    d                    +                    1                                                  n                            ⁢                                                          ⁢                              (                i                )                                                                    ∏                                  j                  =                  1                                d                            ⁢                                                          ⁢                              (                j                )                                              .                                    (        5        )            F(144, 28) would require 197 bits of precision in the numerator and 98 bits of precision in the denominator to produce a 99 bit quotient. Since most digital signal processors (DSPs) used in today's handheld devices typically support only 16 bit×16 bit multiply operations, special multi-precision multiply/divide routines would need to be employed. Such routines require a series of nested multiply/accumulate operations that typically require on the order of k multiple/accumulate (MAC) operations, where k is the number of 16 bit segments in the operand. For a 197 bit operand, k=┌197/161┐=13. So, execution of a single 197×16 bit multiply would require a minimum of 13 MAC operations plus shifting and store operations. The denominator term is calculated in a similar manner to produce a 98 bit result. In addition, a 197/98 bit division is required, which is an extremely complex operation. Thus computation of the entire factorial relation in Eq. 5 would require considerable resources. While prior art methods have addressed these complexity issues to some degree, large values of n and d still may require significant processing resources. Therefore a need exists for a method and apparatus for simplifying the technique utilized for F(n,d).
Skilled artisans will appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions and/or relative positioning of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of various embodiments of the present invention. Also, common but well-understood elements that are useful or necessary in a commercially feasible embodiment are often not depicted in order to facilitate a less obstructed view of these various embodiments of the present invention. It will further be appreciated that certain actions and/or steps may be described or depicted in a particular order of occurrence while those skilled in the art will understand that such specificity with respect to sequence is not actually required. Those skilled in the art will further recognize that references to specific implementation embodiments such as “circuitry” may equally be accomplished via either on general purpose computing apparatus (e.g., CPU) or specialized processing apparatus (e.g., DSP) executing software instructions stored in non-transitory computer-readable memory. Additionally, the elements within the figures exist within a tangible apparatus or electronic device. It will also be understood that the terms and expressions used herein have the ordinary technical meaning as is accorded to such terms and expressions by persons skilled in the technical field as set forth above except where different specific meanings have otherwise been set forth herein.